/*
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

执行用时 :440 ms, 在所有 C++ 提交中击败了11.24%的用户
内存消耗 :6.5 MB, 在所有 C++ 提交中击败了100.00%的用户

复杂度分析：
双层嵌套，O( n^2 )

strcpy和memcpy的区别
strcpy和memcpy都是标准C库函数，它们有下面的特点。
strcpy提供了字符串的复制。即strcpy只用于字符串复制，并且它不仅复制字符串内容之外，还会复制字符串的结束符。

已知strcpy函数的原型是：char* strcpy(char* dest, const char* src);
memcpy提供了一般内存的复制。即memcpy对于需要复制的内容没有限制，因此用途更广。
*/
#include <iostream>
#include <string.h>
using namespace std;
class Solution {
public:
    string longestPalindrome(string s) {
        char* p = &s[0];
        char ans[1002];
        string output;
        if(s ==""){     //!空串
            return s;
        }
        int maxlen = 0, i = 0, j = s.size() - 1;
        int r = 0, w = s.size() - 1;
        for (; r <= w; r++) {    //!边界
            i = r;
            j = w;
            if (j - i + 1 <= maxlen) {      //剪枝
                break;
            }
            while (i <= j) {//只是找到以i开头的回文串, !边界
                int t = i, e = j;
                int tmplen = 0;
                for (; e >= t; e--, t++) {
                    if (p[t] != p[e]) {
                        tmplen = 0;
                        break;
                    }
                    if (e == t) {
                        tmplen++;
                    }
                    else {
                        tmplen += 2;
                    }
                }
                if (tmplen > maxlen) {
                    maxlen = tmplen;
                    memcpy(ans, &p[i], maxlen * sizeof(char));
                    ans[maxlen] = '\0';     //结束符
                }
                j--;
            }
        }
        output = ans;
        return output;
    }
};


int main(int argc, char const* argv[])
{
    Solution s;
    string ss = "babad";
    cout << s.longestPalindrome(ss) << endl;;
    return 0;
}